package com.shm.leetcode;

/**
 * 剑指 Offer 68 - II. 二叉树的最近公共祖先
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 * 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
 *
 *
 *
 *
 *
 * 示例 1:
 *
 * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 * 输出: 3
 * 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
 * 示例 2:
 *
 * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 * 输出: 5
 * 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
 *
 *
 * 说明:
 *
 * 所有节点的值都是唯一的。
 * p、q 为不同节点且均存在于给定的二叉树中。
 * 注意：本题与主站 236 题相同：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 * @author SHM
 */
public class LowestCommonAncestor {
    TreeNode ans;

    /**
     * 方法一：递归
     * 思路和算法
     *
     * 我们递归遍历整棵二叉树，定义 f_xf
     * x
     * ​
     *   表示 xx 节点的子树中是否包含 pp 节点或 qq 节点，如果包含为 true，否则为 false。那么符合条件的最近公共祖先 xx 一定满足如下条件：
     *
     * (f_{\text{lson}}\ \&\&\ f_{\text{rson}})\ ||\ ((x\ =\ p\ ||\ x\ =\ q)\ \&\&\ (f_{\text{lson}}\ ||\ f_{\text{rson}}))
     * (f
     * lson
     * ​
     *   && f
     * rson
     * ​
     *  ) ∣∣ ((x = p ∣∣ x = q) && (f
     * lson
     * ​
     *   ∣∣ f
     * rson
     * ​
     *  ))
     *
     * 其中 \text{lson}lson 和 \text{rson}rson 分别代表 xx 节点的左孩子和右孩子。初看可能会感觉条件判断有点复杂，我们来一条条看，f_{\text{lson}}\ \&\&\ f_{\text{rson}}f
     * lson
     * ​
     *   && f
     * rson
     * ​
     *   说明左子树和右子树均包含 pp 节点或 qq 节点，如果左子树包含的是 pp 节点，那么右子树只能包含 qq 节点，反之亦然，因为 pp 节点和 qq 节点都是不同且唯一的节点，因此如果满足这个判断条件即可说明 xx 就是我们要找的最近公共祖先。再来看第二条判断条件，这个判断条件即是考虑了 xx 恰好是 pp 节点或 qq 节点且它的左子树或右子树有一个包含了另一个节点的情况，因此如果满足这个判断条件亦可说明 xx 就是我们要找的最近公共祖先。
     *
     * 你可能会疑惑这样找出来的公共祖先深度是否是最大的。其实是最大的，因为我们是自底向上从叶子节点开始更新的，所以在所有满足条件的公共祖先中一定是深度最大的祖先先被访问到，且由于 f_xf
     * x
     * ​
     *   本身的定义很巧妙，在找到最近公共祖先 xx 以后，f_xf
     * x
     * ​
     *   按定义被设置为 true ，即假定了这个子树中只有一个 pp 节点或 qq 节点，因此其他公共祖先不会再被判断为符合条件。
     *
     * 下图展示了一个示例，搜索树中两个节点 9 和 11 的最近公共祖先。
     * 复杂度分析
     *
     * 时间复杂度：O(N)O(N)，其中 NN 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)O(N)。
     *
     * 空间复杂度：O(N)O(N) ，其中 NN 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 NN，因此空间复杂度为 O(N)O(N)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-6fdt7/
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        return ans;
    }

    boolean dfs(TreeNode root,TreeNode p,TreeNode q){
        if(root==null){
            return false;
        }
        boolean lson = dfs(root.left,p,q);
        boolean rson = dfs(root.right,p,q);
        if((lson&&rson)||(root.val==p.val||root.val==q.val)&&(lson||rson)){
            ans = root;
        }
        return lson||rson||(root.val==p.val||root.val==q.val);
    }


    //找到两节点得最近祖先
    public TreeNode findAncestor(TreeNode root,int p,int q) {
        if(root==null||root.val==p||root.val==q){
            return root;
        }
        TreeNode left = findAncestor(root.left,p,q);
        TreeNode right = findAncestor(root.right,p,q);
        if(left!=null&&right!=null){
            return root;
        }
        return left==null?right:left;
    }
}
